//垃圾陷阱  转化为分组背包
#include <iostream>
#include <algorithm>

using namespace std;
const int MAXG = 100;
const int MAXT = 1000;
const int INF = 1000000;
int d, g;
struct LaJi {
    int t, f, h;
    bool operator < (const LaJi other) const {
        return t < other.t;
    }
};
LaJi lajies[MAXG + 1];
int maxh[MAXT + 1];//maxh[i]表示在时间i时能够达到的最大高度

int main() {
    cin >> d >> g;

    for (int i = 1; i <= g; i++) {
        int t, f, h;
        cin >> t >> f >> h;
        lajies[i] = {t, f, h};
    }

    sort(lajies, lajies + g + 1);
    int maxt = lajies[g].t;

    for (int i = 1; i <= maxt; i++)
        if (i <= 10)
            maxh[i] = 0;
        else
            maxh[i] = -1 * INF;

    for (int i = 1; i <= g; i++)
        for (int t1 = maxt; t1 >= 1; t1--) {
            if (t1 >= lajies[i].t)  //当前垃圾用来推积
                maxh[t1] = maxh[t1] + lajies[i].h;

            for (int t2 = max(t1 - lajies[i].f, 1); t2 <= t1; t2++) //当前垃圾吃
                if (t2>=lajies[i].t) maxh[t1] = max(maxh[t1], maxh[t2]);

        }

    int ans_i = 0;

    for (int i = 1; i <= maxt; i++){
        if (maxh[i] >= d) {//最早推积高度超过d
            cout << i;
            return 0;
        } else if (maxh[i] < 0){ //第一个无法到达的时间点，它的推积高度为负数
            ans_i = i;
            break;
        }
    }
    
    if (ans_i>0) cout << ans_i-1;
    else {//全部时间点都能到达，但高度始终不够
        int s=10;
        for(int i=1;i<=g;i++) s+=lajies[i].f;
        cout<<s;
    }
}